#include <stdio.h>
#include <stdlib.h>

#define datatype int 

#define num 8
const int  killer = 3;


struct node_st          //创建一个节点（结构体），结构体里包含一个数据和一个指向下一节点的指针
{
	datatype data ;
	struct node_st *next;
};

struct node_st *node_creat(int n)       //  创建一个节点（函数）
{
	int i =1;
	int j = 0;
	struct node_st *me,*home;
	
	me =(struct node_st *)malloc(sizeof (*me));		//注意报错 malloc的返回值为一个（void *）类型的返回值 
    if(me ==NULL)
        return NULL;

	home =me;
	me ->data = i;		    //初始化完一个单向链表 链表的元素的个数只有一个
	me ->next =me;          //节点的指针指向自己
	i ++;
	
	for(; i<= n; i++)
	{
		struct node_st *newnode ;
		newnode = (struct node_st *)malloc(sizeof (*newnode));
		newnode->data = i;
		newnode->next = home;	
			
		me -> next = newnode;
		me = newnode;
	}

	return home;		//设置一个起点，然后将起点返回 
}

void node_show (struct node_st *list)   //  此函数用于显示所有的链表节点
{
	struct node_st * me= list;

	do
	{
		printf("%d ",list ->data);		
		list = list ->next;
	}while(list ->next != me); 
	printf("%d",list->data);



}


//约瑟夫算法 按照约瑟夫环进行删除  
void node_kill (struct node_st *list,int n)			//验证成功！！ 
{
	if(n<0 || n>)
	return 1;
	 
	struct node_st *me =list,*cur;
	int tem = n;

	
	while(list->next != list)				//while循环 条件为知道找到头结点的下一节点是自己则结束循环 说明链表中只有一个节点了 
	{
		for(int i = 0;i <tem -2 ;i++)		//for循环用于寻找合适的“Killer” 	这里寻找的是要Kill 的前驱节点 
		{
			list =list->next;				//链表一直向后寻找 
		}
		
		cur = list->next;					//找到后链表 将链表继续链接至下一节点 
		list->next = cur->next;
		
		printf("%d ",cur->data);
		
		list =list->next;					 
		free(cur);							//释放节点，并将指针设置为空，防止出现野指针 
		
		cur =NULL;
	}
	printf("%d",list->data); 
}

 
int main ()
{
	struct node_st *list;
	
	list = node_creat(num);
		if(list == NULL)
		exit(1);
	

	node_show(list);
	printf("\n");	
	node_kill(list ,killer); 

//	
//	node_union		//用于合并两个链表 
//	
	
	
	
	exit (0);
}

